import java.util.ArrayList;
import java.util.List;

public class Solution212 {

    List<String> res;
    boolean[][] visited;
    MyTrie trie;

    public List<String> findWords(char[][] board, String[] words) {
        int m = board.length;
        int n = board[0].length;
        res = new ArrayList<>();
        visited = new boolean[m][n];
        trie = new MyTrie();
        for (String word : words) {
            trie.insert(word);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, trie);
            }
        }
        return res;
    }

    void dfs(char[][] board, int i, int j, MyTrie node) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || visited[i][j]) {
            return;
        }
        node = node.children[board[i][j] - 'a'];
        if (node == null) {
            return;
        }
        visited[i][j] = true;
        if (node.isEnd) {
            res.add(node.s);
            node.isEnd = false;
        }
        dfs(board, i - 1, j, node);
        dfs(board, i + 1, j, node);
        dfs(board, i, j + 1, node);
        dfs(board, i, j - 1, node);
        visited[i][j] = false;
    }
}

class MyTrie {
    MyTrie[] children;
    boolean isEnd;
    String s;

    public MyTrie() {
        children = new MyTrie[26];
        isEnd = false;
    }

    public void insert(String word) {
        MyTrie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new MyTrie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
        node.s = word;
    }
}